#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.


"""
    寻找欧拉path(euler path不用回到原点, euler circuit必须回到原点)
    这里处理的是无向图: 有向图处理方式相同.

    输入edges: 这里假设输入的图是一个连通无向图, 即不存在多个连通分量(也不可能存在孤立节点.)

    过程:
        欧拉回路

        输入edges
        生成邻接表

        判断度数，

        如果两个度数，调整一个b 作为neigh 在另一个a在首位
        a放入ready_handle

        从a作为start开始dfs

        判断edge是否处理过，处理过就跳过
        每次把edge 标记为处理过，每次标记处理过的节点
        每次标记度已经完毕的节点（依旧有度，并且已经处理过的作为ready_handle容器）
        如果回到start
        从ready_handle的节点中选择一个作为start
        继续dfs，直到回到start（如果没有回到start，表示没有欧拉回路，结束程序（理论上判断完度数，一定可以回到）），继续上述过程

        直到ready_handle结束（判断是否所有边都完毕）
        判断是否所有节点都处理过（理论处理完毕，否则图不联通）
"""


from collections import defaultdict


class GraphNode:
    def __init__(self, label):
        self.label = label
        self.neighbors = []     # nei_label list

    def add(self, nei_label):
        if nei_label not in self.neighbors:
            self.neighbors.append(nei_label)

    def __str__(self):
        return str(self.label)


class EulerPath:
    def __init__(self, edges):
        self.edges = set(edges)         # 因为访问过程中可能会删除, 所以这里进行一次copy
        self.nodes = {}                 # {label : node}
        self.degree = defaultdict(int)  # {label : degree}
        self.nei_idx = defaultdict(int) # {label : idx} :表示某个节点的邻接节点遍历到哪里了
        self.ready_handle = set()
        self.result_path = []

        self._build_from_edges()

        # get first start/ end node
        # 如果起点和终点必须相同: 那么这里self.start_euler_node 和 self.end_euler_node设置为相同
        self.start_euler_node, self.end_euler_node = self._get_euler_first_node()
        if self.start_euler_node is None:
            print('has no euler path for edges')
            return

        self.ready_handle.add(self.start_euler_node)

        # do-while's "do part"
        self.tmp_path = []
        # print('start node %s' % self.start_euler_node)
        # print('result_path node %s' % self.result_path)
        # print('tmp_path node %s' % self.tmp_path)
        # print('remain edges node %s' % self.edges)
        # print('===================  =====================')
        self._do_euler_dfs(self.start_euler_node)

        while self.ready_handle and self.edges:
            # print('result_path node %s' % self.result_path)
            # print('tmp_path node %s' % self.tmp_path)
            # print('remain edges node %s' % self.edges)
            # print('===================  =====================')

            self.tmp_path = []
            self.start_euler_node = self._get_set(self.ready_handle)
            self.end_euler_node = self.start_euler_node
            # print('start node %s' % self.start_euler_node)
            self._do_euler_dfs(self.start_euler_node)

        assert not (self.ready_handle and self.edges)

        # print(self.nodes)
        # print(self.ready_handle)
        # print(self.degree)

    def _build_from_edges(self):
        for start, end in self.edges:
            start_node = self._get_node(start)
            end_node = self._get_node(end)

            start_node.add(end_node)
            end_node.add(start_node)

            # 记录degree: 一条edge相当于两个degree(所以degree总数为偶数, 这也是一条定理)
            # 所以一定有偶数个奇点.
            self.degree[start] += 1
            self.degree[end] += 1

    def _get_euler_first_node(self):
        odd_degree_node = []
        for label, degree in self.degree.items():
            if degree % 2 == 1:
                odd_degree_node.append(label)

        # 总度数为偶数(等于edge * 2), 所以odd个数应该为偶数.
        odd_len = len(odd_degree_node)
        assert  odd_len % 2 == 0

        if odd_len > 2:
            return None, None

        # 不可能发生odd_len == 1的情况(一定是偶数)

        # NOTE: 如果起点和终点必须相同, 那么odd_len 必须为0
        if odd_len == 2:
            first_label = odd_degree_node[0]
            second_label = odd_degree_node[1]

            first_node = self.nodes[first_label]
            second_node = self.nodes[second_label]

            print('can start at %s point, end at %s node. or inverse' % (first_node, second_node))

            if first_node.neighbors[0] is not second_node:
                first_node.neighbors.remove(second_node)
                first_node.neighbors.insert(0, second_node)

            return first_node, second_node

        if odd_len == 0:
            print('can start at any point, end at same node')
            node = self._get_dict(self.nodes)
            return node, node

    def _do_euler_dfs(self, node):
        handle_idx = self.nei_idx[node.label]
        # if handle_idx > len(node.neighbors):
        #     # 需要在这里做valid判断吗?
        #     self.ready_handle.remove(node)
        #     return

        nei = self._next_valid_child(node, handle_idx)
        # print(type(nei))
        if not nei:
            return

        self.ready_handle.add(nei)
        self.tmp_path.append( nei.label )

        # 判断是否回到self.start_node
        if nei is self.end_euler_node:
            # 插入开头 start_node
            self.tmp_path.insert(0, self.start_euler_node.label)
            # print('match start %s, end %s: tmp_path %s, ' % (self.start_euler_node, self.end_euler_node, self.tmp_path))

            self._connect_path(self.tmp_path)
            return

        self._do_euler_dfs(nei)

    def _connect_path(self, tmp_path):
        if not self.result_path:
            self.result_path.extend(tmp_path)
        else:
            insert_idx = self.result_path.index(tmp_path[0])
            self.result_path[insert_idx:insert_idx+1] = tmp_path

    def _next_valid_child(self, node, handle_idx):
        nei_len = len(node.neighbors)

        while handle_idx < nei_len:
            nei = node.neighbors[handle_idx]
            # if (node.label, nei.label) not in self.edges and (nei.label, node.label) not in self.edges:
            if (node.label, nei.label) in self.edges:
                self.edges.remove((node.label, nei.label))
                handle_idx += 1
                return nei
            elif (nei.label, node.label) in self.edges:
                self.edges.remove((nei.label, node.label))
                handle_idx += 1
                return nei
            else:
                handle_idx += 1     # 表示这次处理过了

        self.ready_handle.remove(node)
        return None

    def _get_dict(self, d):
        label, node = d.popitem()
        d[label] = node
        return node

    def _get_set(self, s):
        node = s.pop()
        s.add(node)
        return node

    def _get_node(self, label):
        node = self.nodes.get(label)
        if node is None:
            node = GraphNode(label)
            self.nodes[label] = node
        return node


def test_euler_path():
    edges = [
        (1,2),
        (2,3),
        (3,1),
        ]

    # page 246
    example1 = [
        ('A', 'B'),
        ('A', 'C'),
        ('A', 'F'),

        ('B', 'D'),
        ('B', 'F'),

        ('C', 'E'),
        ('C', 'F'),
        ('C', 'D'),

        ('D', 'E'),
        ('D', 'F'),
    ]

    # page 247
    example2 = [
        (1, 3),
        (1, 4),

        (2, 3),
        (2, 8),

        (3, 4),
        (3, 6),
        (3, 7),
        (3, 9),

        (4, 5),
        (4, 7),
        (4, 10),
        (4, 11),

        (5, 10),

        (6, 9),

        (7, 9),
        (7, 10),

        (8, 9),

        (9, 10),
        (9, 12),

        (10, 11),
        (10, 12),
    ]

    ep = EulerPath(example1)

    print(len(example2))
    print(len(ep.result_path) - 1)

    print('result %s' % ep.result_path)

def main():
    print("start main")
    test_euler_path()

if __name__ == "__main__":
    main()
